function bubbleSort(list, type = 1) {
  const len = list.length;
  for (let i = 0; i < len; ++i) {
    let noExchange = true;
    for (let j = 0; j < len - i - 1; ++j) {
      let mustExchange =
        type == 1 ? list[j] > list[j + 1] : list[j] < list[j + 1];
      if (mustExchange) {
        noExchange = false;
        [list[j], list[j + 1]] = [list[j + 1], list[j]];
      }
    }

    if (noExchange) break;
  }
  return list;
}

function insertionSort(list, type = 1) {
  const len = list.length;
  if (len == 1) return list;

  for (let i = 1; i < len; ++i) {
    const value = list[i];
    let j = i - 1;
    for (; j >= 0; --j) {
      let mustMove = type == 1 ? list[j] > value : list[j] < value;
      if (mustMove) {
        list[j + 1] = list[j];
      } else {
        break;
      }
    }
    list[j + 1] = value;
  }
  return list;
}

function mergeSort(list, type = 1) {
  const len = list.length;
  const tmp = new Array(len);
  const isAscending = type == 1;

  function _merge(list, l1, r1, l2, r2) {
    let start = (i = l1);

    while (r1 >= l1 && r2 >= l2) {
      tmp[i++] = isAscending
        ? list[l1] > list[l2]
          ? list[l2++]
          : list[l1++]
        : list[l1] < list[l2]
        ? list[l2++]
        : list[l1++];
    }

    while (l1 <= r1) {
      tmp[i++] = list[l1++];
    }

    while (l2 <= r2) {
      tmp[i++] = list[l2++];
    }

    while (--i >= start) {
      list[i] = tmp[i];
    }
  }

  function _mergeSort(list, l, r) {
    if (l < r) {
      if (r - l == 1) {
        if (
          (isAscending && list[l] > list[r]) ||
          (!isAscending && list[l] < list[r])
        ) {
          [list[l], list[r]] = [list[r], list[l]];
        }
      } else {
        let l1 = l;
        let r1 = parseInt((l + r) / 2);
        let l2 = r1 + 1;
        let r2 = r;
        _mergeSort(list, l1, r1);
        _mergeSort(list, l2, r2);
        _merge(list, l1, r1, l2, r2);
      }
    }
  }

  _mergeSort(list, 0, len - 1);
  return list;
}

function performance(name, fn, ...args) {
  let start = new Date();
  console.log(name, "开始时间", start);
  let res = fn(...args);
  let end = new Date();
  console.log(name, "结束时间", end);
  console.log(name, "共耗时：", (end.getTime() - start.getTime()) / 1000, "秒");
  return res;
}

function listChecker(...lists) {
  let listsLen = lists.length;
  let len = lists[0].length;
  let tmpVal;

  if (!listsLen) {
    return console.error("必须有对比的数据");
  }

  for (let i = 1; i < lists.length; i++) {
    if (lists[i].length !== len) {
      console.error(`第 ${i} 个list 长度不一致`);
      return;
    }
  }

  for (let i = 0; i < len; i++) {
    for (let j = 1, tmpVal = lists[0][i]; j < listsLen; j++) {
      if (lists[j][i] !== tmpVal) {
        return console.error(`第 ${i} 个list 第 ${j} 个数据不一致`);
      }
    }
  }

  console.log("数据完全一致");
}

let count = 10000000;
let list = new Array(count);
let minVal = 10;
let maxVal = 1000;
for (let i = 0; i < count; i++) {
  list[i] = minVal + Math.random() * (maxVal - minVal) | 0;
}
console.log("before", list.slice());
// console.log("after", performance("bubbleSort", bubbleSort, list.slice(), -1));
// const insertionList = performance(
//   "insertionSort",
//   insertionSort,
//   list.slice(),
//   -1,
// );
// console.log("after insertionSort", insertionList);

const mergeList = performance("mergeSort", mergeSort, list.slice(), -1);
console.log("after mergeSort", mergeList);

// listChecker(insertionList, mergeList);
